P10858 [HBCPC2024] Long Live 题解

0x00 题目大意

对于两个给定的正整数 $x$ 和 $y$，找到另两个整数 $a$ 和 $b$ 满足：

$$\sqrt{\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}}=a\sqrt{b}$$

求当 $a\times b$ 最小时 $a$ 和 $b$ 的值。

0x01 解题思路

求出 $\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}=k$，代入原式：

$$\sqrt{k}=a\sqrt{b}$$

左右平方：

$$k=a^2b$$

此时要使得 $ab$ 最小，则要使得 $a$ 最小（$a^2b=a(ab)$），故直接令 $a=1$ 即可得最优答案。

0x02 AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int x,y;
    cin>>x>>y;
    int ans=x*y/__gcd(x,y)/__gcd(x,y);
    cout<<1<<" "<<ans<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}